package com.cjl.interview150.list;

import org.junit.jupiter.api.Test;

import java.util.*;

public class ListPractice {

    public boolean hasCycle(ListNode head) {
        // 定义hashSet用于去重
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
            // 如果返回false代表添加过
            if (!set.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

    public boolean hasCycle2(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        // 定义快慢指针,如果有环则快慢指正必定相遇
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    /**
     * 2. 两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 定义head和tail表示新链表
        ListNode head = null, tail = null;
        // 定义进位数
        int carry = 0;
        while (l1 != null || l2 != null) {
            // 获取当前节点的值,如果其中一个为null则补0
            int num1 = l1 == null ? 0 : l1.val;
            int num2 = l2 == null ? 0 : l2.val;
            // 计算当前节点的值
            int sum = num1 + num2 + carry;
            // 判断head是否为null,后续需要通过tail构造链表
            if (head == null) {
                // 加入新节点时需要考虑进位
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            // 更新进位
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 判断最后还有没有进位值
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    /**
     * 138. 随机链表的复制(利用hash表保存映射关系)
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        // 1.利用hashMap保存原节点和新节点的映射关系：原节点->新节点
        HashMap<Node, Node> map = new HashMap<>();
        // 2.复制原节点创建新节点,并建立映射关系
        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 3.根据映射关系构建每个节点的next和random
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 4.返回原先节点head的映射即为新构建的头节点
        return map.get(head);
    }

    /**
     * 92. 反转链表 II
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 1.定义虚拟头节点统一后续操作
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 定义临时指针
        ListNode pre = dummy;
        // 2.pre走left - 1步来到left前一个节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        // 3.再走right - left + 1来到right这个节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        // 4.切割出一个子链表(用新的节点保存left和right并切割)
        ListNode leftNode = pre.next;
        ListNode after = rightNode.next;
        // 5.切断链表并反转
        pre.next = null;
        rightNode.next = null;
        reverseLinkedList(leftNode);
        // 6.重新连接并返回
        pre.next = rightNode;
        leftNode.next = after;
        return dummy.next;
    }

    // 反转链表
    private void reverseLinkedList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }

    /**
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        // 创建虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 创建辅助指针
        ListNode p = dummy;
        // 不断判断下一个节点和下下个节点的val是否相等
        while (p.next != null && p.next.next != null) {
            if (p.next.val == p.next.next.val) { // 如果相等则循环删除
                int x = p.next.val;
                while (p.next != null && p.next.val == x) {
                    p.next = p.next.next;
                }
            } else {
                p = p.next;
            }
        }
        return dummy.next;
    }

    /**
     * 61. 旋转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        // 如果链表为空或者只有一个元素或者移动的元素为0则直接返回头节点
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        int len = 1;
        ListNode p = head;
        // 计算链表长度
        while (p.next != null) {
            p = p.next;
            len++;
        }
        // 计算需要指针后移的距离
        int move = len - k % len;
        if (move == len) {
            // 说明不需要移动
            return head;
        }
        // 连接链表成环
        p.next = head;
        // p在原始链表的尾元素，需要让其移动add个元素到达新链表的尾元素
        while (move-- > 0) {
            p = p.next;
        }
        // 此时p.next则是新的头节点
        ListNode resNode = p.next;
        // 截断链表
        p.next = null;
        return resNode;
    }

    /**
     * 86. 分隔链表
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        // 定义两个链表，small和big
        ListNode smallList = new ListNode(0);
        ListNode bigList = new ListNode(0);
        // 定义辅助指针
        ListNode small = smallList;
        ListNode big = bigList;
        // 循环遍历，将大于等于x的加入bigList，小于的加入smallList
        while (head != null) {
            int val = head.val;
            if (val < x) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }
            // head后移
            head = head.next;
        }
        // 将small尾部接到big的第一个节点
        small.next = bigList.next;
        // 置空尾节点
        big.next = null;
        // 返回small List后一个节点即为新的头节点
        return smallList.next;
    }
}

/**
 * 146. LRU 缓存
 */
class LRUCache extends LinkedHashMap<Integer,Integer> {

    private int capacity;

    public LRUCache(int capacity) {
        super(capacity,0.75F,true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
